<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>

<body>
    <script>
        // 动态规划
        // 1. 一袋硬币 面值[1, 2, 5], 总价11（ 选做）
        // 请问如何让硬币数量最小, 凑齐11
        // var coins = function(parValue) {
        //     var coin = [];
        //     var num = Math.floor(parValue / 5);
        //     var index = parValue % 5;
        //     for (var i = 0; i < num; i++) {
        //         coin.push(5);
        //     }
        //     while (index != 1 && index > 0) {
        //         index = index - 2;
        //         coin.push(2);
        //     }
        //     if (index == 1) {
        //         coin.push(1);
        //     }
        //     console.log(coin);
        // }
        // coins(3);

        var coinChange = function(amount) {
            //用一个数组记录一下，1-amount需要硬币的最小数量
            var dps = new Array(amount + 1); //1-11
            var coins = [1, 2, 5];
            //从1开始算出到amount（11）算出组成
            //amount需要硬币数量的最小值
            dps[0] = 0;
            for (var i = 1; i < amount + 1; i++) {
                dps[i] = amount + 1;
                //先赋值大于amount的值，为了应付任何硬币组合都无法成立的情况
                for (var j = 0; j < coins.length; j++) {
                    if (i >= coins[j]) {
                        dps[i] = Math.min(dps[i], dps[i - coins[j]] + 1);
                    }
                }
            }
            return dps[amount] == amount + 1 ? false : dps[amount];
        }
        console.log(coinChange(13));
        //dps[0]   --0
        //dps[1]   --1
        //dps[2]   --1
        //dps[3]   --2
        //dps[4]   --2



        // 2. 给出一个字符串, 让字符串中重复的字母删除掉, 不影响字符串字母原来的顺序的情况下, 按字典顺序输出的值为最小

        var sortByDictionary = function(s) {
            var arr = [];
            var chars = []; //记录下标值
            var j = 0;
            //制作字符串对应的index数组
            //chars记录一下究竟有哪几个字母用到了
            for (var i = 0; i < s.length; i++) {
                var c = s.charAt(i);
                if (arr[c]) {
                    arr[c].push(i);
                } else {
                    chars.push(c);
                    arr[c] = [i];
                    j++;
                }
            }
            arr.length = j;
            //让这个字母从小到大排序
            chars.sort();
            var ret = [];
            for (var i = 0; i < arr.length; i++) {
                if (arr.length == 1) {
                    //如果index数组只剩下一个，那么把他对应的字母压栈，然后返回
                    ret.push(chars[0]);
                    break;
                }
                var src = arr[chars[i]];
                var idx = src[0];
                var isOk = true;
                //根据index数组计算一下当前字母是否可行
                for (var j = i + 1; j < arr.length; j++) {
                    var des = arr[chars[j]];
                    if (idx > des[des.length - 1]) {
                        isOk = false;
                        break;
                    }
                }
                //如果可行
                if (isOk) {
                    //删除idx之前的那些数字
                    for (var j = 0; j < arr.length; j++) {
                        if (i !== j) {
                            var tempArr = arr[chars[j]];
                            var deleteLen = 0
                            for (var k = 0; k < tempArr.length; k++) {
                                if (tempArr[k] < idx) {
                                    deleteLen++;
                                }
                            }
                            tempArr.splice(0, deleteLen);
                        }
                    }
                    //制作答案（把当前字母压栈
                    ret.push(chars[i]);
                    //删除这个字母
                    delete arr[chars[i]];
                    arr.length--;
                    //从字母数组中也删除
                    chars.splice(i, 1);
                    //重新开始计算下一个目标
                    i = -1;
                }
            }
            return ret;
        }
        console.log(sortByDictionary("cacdcc"));




        // 3. 给你一个整数（ 100 以内）, 转换成罗马数字
        // 1 - 9 Ⅰ－ 1、 Ⅱ－ 2、 Ⅲ－ 3、 Ⅳ－ 4、 Ⅴ－ 5、 Ⅵ－ 6、 Ⅶ－ 7、 Ⅷ－ 8、 Ⅸ－ 9
        // 10 - 90
        // Ⅹ－ 10、 Ⅺ－ 11、 Ⅻ－ 12、 XIII－ 13、 XIV－ 14、 XV－ 15、 XVI－ 16、 XVII－ 17、 XVIII－ 18、 XIX－ 19、
        // XX－ 20、 XXI－ 21、 XXII－ 22、 XXIX－ 29、
        // XXX－ 30、 XXXIV－ 34、 XXXV－ 35、 XXXIX－ 39、
        // XL－ 40、
        // L－ 50、 LI－ 51、 LV－ 55、
        // LX－ 60、 LXV－ 65、
        // LXXX－ 80、
        // XC－ 90、
        var LuoMa = function(num) {
            if (num < 100 && num > 0) {
                var nums = [];
                var g = ['', 'Ⅰ', 'Ⅱ', 'Ⅲ', 'Ⅳ', 'Ⅴ', 'Ⅵ', 'Ⅶ', 'Ⅷ', 'Ⅸ'];
                var s = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'];
                num = num + "";
                for (var q = 0; q < num.length; q++) {
                    nums.push(num.slice(q, q + 1));
                }
                if (num.length == 1) {
                    var LuoMaNum = g[Number(nums[0])];
                } else {
                    var sw = s[Number(nums[0])];
                    var gw = g[Number(nums[1])];
                    var LuoMaNum = sw + gw;
                }

                console.log(LuoMaNum);
            }

        }
        LuoMa(9);
    </script>
</body>

</html>